package com.desin.modle.datastruct.algo.DynamicAlgorithm.minLujing;

public class Solution {
    public int minDest = Integer.MAX_VALUE;

    public void test1(int i,int j,int dest,int[][] data){
        int length = data.length;
        if(i==length&&j==length){
            dest = dest + data[i][j];
            if(dest<minDest){
                minDest = dest;
            }
            System.out.println("最短路径: "+ minDest);
            return;
        }
        if(i<length){
            test1(i+1,j,dest+data[i+1][j],data);
        }
        if(j<length){
            test1(i,j+1,dest+data[i][j+1],data);
        }
    }

    public int[][] results = new int[4][4];

    public int test2(int i,int j,int[][] data){
        if(i==0&&j==0){
            return data[0][0];
        }
        if(results[i][j]>0){
            return results[i][j];
        }
        int lowerMin = Integer.MAX_VALUE;
        if(i-1>=0){
            lowerMin = test2(i-1,j,data);
        }
        int rightMin = Integer.MAX_VALUE;
        if(j-1>=0){
            rightMin = test2(i,j-1,data);
        }
        int curMin = data[i][j]+Math.min(lowerMin,rightMin);
        results[i][j] = curMin;
        return curMin;
    }

    public int test3(int[][] data){
        int length = data.length;
        int[][] states = new int[length][length];


        for(int i=0;i<length;i++){
            for(int j=0;j<length;j++){
                states[i][j] = -1;
            }
        }

        int sum=0;
        for(int i=0;i<length;i++){
            sum = sum + data[0][i];
            states[0][i]=sum;
        }
        sum=0;
        for(int i=0;i<length;i++){
            sum = sum + data[i][0];
            states[i][0] = sum;
        }

        for(int i=1;i<length;i++){
            for(int j=1;j<length;j++){
                states[i][j] = data[i][j] + Math.min(states[i-1][j],states[i][j-1]);
            }
        }
        return states[length-1][length-1];
    }
}
